package com.mhg.fondamental.arr;

class Demo_Array_Selection
{
	//算法 3 二分查表法 查询指定元素的索引 有就返回索引 无返回-1
	public static void main(String[] args) 
	{
		int[] arr = {10,2,4,7,19,8};
		//二分查找法有前提 必须是有序数组
		print(arr);//遍历 排序前
		sort(arr);//排序
		print(arr);//遍历 排序后
		//使用二分法 查找 10 在数组中第一次出现的位置
		int index = findIndex(arr,10);
		System.out.println("10的角标是:::"+index);
	}
	/*
		二分查表法 方法抽取
			1.方法名 findIndex
			2.参数列表 数组 值
			3.返回值类型 int 角标
	*/
	public static int findIndex(int[] arr,int value){ //{2 4 7 8 10 19} 
		int start = 0;//初始起点						//start = 0
		int end = arr.length-1;//初始终点 最大角标		//end = 5
		int middle = (start+end)/2; //初始中间角标		//middle = (0+5)/2 = 2 
		
		while(arr[middle]!=value){
			if(value>arr[middle]){		
				start = middle + 1;	     
			}else if(value < arr[middle]){
				end = middle - 1;
			}
			if(start > end){ 
				return -1;
			}
			middle = (start+end)/2;  
		}
		return middle;
	}
	/*
		冒泡排序 方法抽取
	*/
	public static void sort(int[] arr){
		for(int i=0;i<arr.length-1;i++){
			for(int j=0;j<arr.length-i-1;j++){
				if(arr[j]>arr[j+1]){
					int temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = temp;
				}
			}
		}
	}
	/*
		遍历数组
	*/
	public static void print(int[] arr){
		for(int i=0;i<arr.length;i++){
			System.out.print(arr[i]+" ");
		}
		System.out.println();
	}
}